#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <string>
#include <queue>
#include <vector>

using namespace std;

#define INF 1<<29
#define eps 1e-8
#define A system("pause")
#define rep(i,h,n) for(int i=(h);i<=(n);i++)
#define ms(a,b) memset((a),(b),sizeof(a))

const int maxn=12;
const int maxm=150000+10;
int map[maxn][maxn],dp[1<<11][maxn],n;//总共只有11种状态； 
inline void floyd()
{
     rep(k,0,n) rep(i,0,n) rep(j,0,n)
     map[i][j]=std::min(map[i][k]+map[k][j],map[i][j]);
}

int main()
{
     while(~scanf("%d",&n)&&n)
     {
          rep(i,0,n) rep(j,0,n) scanf("%d",&map[i][j]);
          floyd();
          for(int s=0;s<(1<<n);s++)//枚举所有状态 
          {
              rep(i,1,n)
              {
                 if(s&&(1<<(i-1)))//经过城市i，分两种情况；只过了i和经过中间城市到i； 
                 {
                      if(s==(1<<(i-1))) dp[s][i]=map[0][i];
                      else 
                      {
                          dp[s][i]=INF;
                          rep(j,1,n)
                          {
                                if(s&(1<<(j-1))&&i!=j)//枚举不是i的其他城市； 
                                dp[s][i]=std::min(dp[s^(1<<(i-1))][j]+map[j][i],dp[s][i]);
                                //在没经过城市I的状态中，寻找合适的中间点J使得距离更短 
                          }
                      }
                 }
              }
          }
          int ret=dp[(1<<n)-1][1]+map[1][0];
          rep(i,1,n) ret=std::min(dp[(1<<n)-1][i]+map[i][0],ret);
          cout<<ret<<endl;
     }
     //A;
     return 0;
}          
